#include "string_array.h"
#include<iostream>
using namespace std;
myStr::myStr(const char* p){
	int i=0;
	while(p[i]!='\0') i++;
	length=i;
	data=new char[100000];
	data[0]=length;
	for(int j=1;j<length+2;j++){
		data[j]=p[j-1];
	}
}
myStr::~myStr(){
}
void myStr::print(){
    for(int i = 1; i < length+1; i++)
        cout << data[i];
    cout << endl;
}
void myStr::kmp_next(){
	next=new int[length+1];
	int j=1,k=0;
	next[1]=0;
	while(j<length){
		if(k==0||data[j]==data[k]){
			++j;++k;next[j]=k;
		}
		else{
			k=next[k];
		}
	}
}
void myStr::printNext(){
    for(int i = 1; i <= length; i++)
        cout << next[i];
    cout << endl;
}
void myStr::kmp_nextVal()
{
	nextVal=new int[length+1];
	int j=1,k=0;
	nextVal[1]=0;
	while(j<length){
		if(k==0||data[j]==data[k]){
			++j;++k;
			if(data[j]!=data[k]){
				nextVal[j]=k;
			}
			else{
				nextVal[j]=nextVal[k];
			}
		}
		else{
			k=nextVal[k];
		}
	}
}
void myStr::printNextVal(){
    for(int i = 1; i <=length; i++)
        cout << nextVal[i];
    cout << endl;
}

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V){
   int x=0;
    int a=start;
    int m=1;
    for(int n = 1; n <= T.length; n++){
        if(S.data[m] == T.data[n]){
            m++;
            x++;
        }
        else if(S.data[m] != T.data[n]){
            a++;
            m = a;
            n = 0;
            x = 0;
        }
        if(a > S.length) break;
    }
    if(x != T.length) return 0;
    int y = a;
    int l;
    int tmp = y;
    if(T.length < V.length){
        l = V.length - T.length;
        for(int i = S.length + 1; i >= y + T.length; i--) S.data[i + l] = S.data[i];
        for(int i = 1; i <= V.length; i++){
            S.data[tmp] = V.data[i];
            tmp++;
        }
        S.length = S.length + l;
    }
    else if(T.length > V.length){
        l = T.length - V.length;
        for(int i = 1; i <= V.length; i++){
            S.data[tmp] = V.data[i];
            tmp++;
        }
        for(int i = y + T.length; i <= S.length + 1; i++) S.data[i - l] = S.data[i];
        S.length = S.length - l;
    }
    else{
        for(int i = 1; i <= V.length; i++){
            S.data[tmp] = V.data[i];
            tmp++;
        }
    }
    return 1;

}
int kmpMatch(const myStr& S, const myStr& T){
	int n=S.length,m=T.length; 
    int i = 1;
    int j = 1;
    while(i <= n && j <= m){
        if(j == 0 || S.data[i] == T.data[j]){
            ++i;
            ++j;
        }
        else j = T.nextVal[j]; 
    }
    if(j > m) return i - m;
    return -1;

}
int simpleMatch(const myStr& S, const myStr& T)
{
	int n=S.length,m=T.length;
	int i=1,j=1;
	while(i<=n&&j<=m){
		if(S.data[i]==T.data[j]){
			++i;++j;
		}
		else{
			i=i-j+2;j=1;
		}
	}
	if(j>m) return i-m;
	else return -1;
}

myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* p){
	rowNum=rNum;
	colNum=cNum;
	nodeNum=nNum;
	matrixNode a;
	nodeList=new matrixNode[10000];
	for(int i=0;i<3*nodeNum;i++){
		if(i%3==0){
			nodeList[i/3].row=p[i];
		}
		if(i%3==1){
			nodeList[i/3].col=p[i];
		}
		if(i%3==2){
			nodeList[i/3].value=p[i];
		}
	}
		for(int i=0;i<nodeNum-1;i++){
		for(int j=0;j<nodeNum-1-i;j++){
			if(nodeList[j].row>nodeList[j+1].row){
				a=nodeList[j+1];
				nodeList[j+1]=nodeList[j];
				nodeList[j]=a;
			}
		}
	}
}

myMatrix::myMatrix(){
	rowNum=0;
	colNum=0;
	nodeNum=0;
	nodeList=new matrixNode[10000];	
}

myMatrix::~myMatrix(){
	delete nodeList;
}

void myMatrix::FastTransposeSMatrix(myMatrix& T){
	T.rowNum=colNum;
	T.colNum=rowNum;
	T.nodeNum=nodeNum;
	int t=0;
	for(int i=1;i<=colNum;i++){
		for(int j=0;j<nodeNum;j++){
			if(nodeList[j].col==i){
				T.nodeList[t].col=nodeList[j].row;
				T.nodeList[t].row=nodeList[j].col;
				T.nodeList[t].value=nodeList[j].value;
				t++;
			}
		}
	}
	
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
